﻿#define  _CRT_SECURE_NO_WARNINGS
//最长子序链
class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {

        int n = pairs.size();
        vector<int>dp(n, 1);
        int Max = 1;

        sort(pairs.begin(), pairs.end());

        for (int i = 1;i < n;i++)
        {
            for (int j = 0;j < i;j++)
            {
                if (pairs[i][0] > pairs[j][1])
                {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }

            Max = max(dp[i], Max);
        }

        return Max;

    }
};

//最长子序列的个数
class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {

        int n = nums.size();
        vector<int>lenth(n, 1);
        vector<int>count(n, 1);
        int recount = 1, relen = 1;

        for (int i = 1;i < n;i++)
        {
            for (int j = 0;j < i;j++)
            {
                if (nums[i] > nums[j])
                {

                    if (lenth[i] == lenth[j] + 1)
                    {
                        count[i] += count[j];
                    }
                    else if (lenth[j] + 1 > lenth[i])
                    {
                        count[i] = count[j];
                        lenth[i] = lenth[j] + 1;
                    }
                }

            }
            if (relen == lenth[i]) recount += count[i];
            else if (relen < lenth[i]) relen = lenth[i], recount = count[i];
        }

        return recount;



    }
};

//最小覆盖字串
class Solution {
public:
    string minWindow(string s, string t) {

        if (s.size() < t.size())
        {
            return "";
        }

        int n = s.size();
        int str[256] = { 0 };
        int debt = t.size();
        int len = 0x3f3f3f3f;
        int start = 0;

        for (int i = 0;i < debt;i++)
        {
            str[t[i]]--;
        }

        for (int r = 0, l = 0;r < n;r++)
        {
            if (str[s[r]] < 0) debt--;
            str[s[r]]++;

            if (debt == 0)
            {
                while (str[s[l]] > 0) str[s[l]]--, l++;
                start = r - l + 1 < len ? l : start;
                len = min(len, r - l + 1);
                str[s[l]]--;
                l++;
                debt++;
            }

        }

        len = len == 0x3f3f3f3f ? 0 : len;

        string str1;
        for (int i = start;i < start + len;i++)
        {
            // cout<<len<<" ";
            str1.push_back(s[i]);
        }

        return str1;




    }
};

//最长定差子序列
class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {

        int n = arr.size();
        unordered_map<int, int>hash;//一个key，一个value,通过key来找value
        hash[arr[0]] = 1;
        int Max = 1;

        for (int i = 1;i < n;i++)
        {
            hash[arr[i]] = hash[arr[i] - difference] + 1;//使用哈希表来代替查找的过程
            Max = max(hash[arr[i]], Max);//找最大值

        }
        return Max;//返回最长
    }
};


//最长的斐波那契数列

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {

        int n = arr.size();

        vector<vector<int>>dp(n, vector<int>(n, 2));

        unordered_map<int, int>hash;

        for (int i = 0;i < n;i++)
        {
            hash[arr[i]] = i;
        }

        int Maxlenth = 2;

        for (int j = 2;j < n;j++)
        {
            for (int i = 1;i < n;i++)
            {
                int num = arr[j] - arr[i];
                if (hash.count(num) && num < arr[i])
                {
                    dp[i][j] = dp[hash[num]][i] + 1;
                }

                Maxlenth = max(Maxlenth, dp[i][j]);
            }
        }

        return Maxlenth == 2 ? 0 : Maxlenth;
    }

};

//长度为k子数组的最大和
class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {

        int n = nums.size();
        unordered_map<int, int>hash;
        long long sum = 0;
        long long ans = 0;
        int count = 0;


        for (int r = 0, l = 0;r < n;r++)
        {
            hash[nums[r]]++;
            sum += nums[r];
            if (hash[nums[r]] > 1) count++;

            if (r - l + 1 == k)
            {
                if (count == 0)
                {
                    ans = max(ans, sum);
                }

                sum -= nums[l];
                if (hash[nums[l]] > 1) count--;
                hash[nums[l]]--;
                l++;
            }
        }

        return ans;

    }
};

//删除字串后字符串的最小长度

class Solution {
public:
    int minLength(string s) {

        stack<char>st;
        int n = s.size();

        for (int i = 0;i < n;i++)
        {
            if (!st.empty() && ((s[i] == 'B' && st.top() == 'A' || s[i] == 'D' && st.top() == 'C')))
            {
                st.pop();
            }
            else
            {
                st.push(s[i]);
            }
        }

        return st.size();


    }
};

//字符串的排列

class Solution {
public:
    bool checkInclusion(string s1, string s2) {

        int k = s1.size();
        int n = s2.size();

        cout << k << " " << n << endl;

        int hash_s1[26] = {};
        int hash_s2[26] = {};

        for (int i = 0;i < k;i++)
        {
            hash_s1[s1[i] - 'a']++;
        }

        bool flag = true;

        for (int l = 0, r = 0;r < n;r++)
        {
            hash_s2[s2[r] - 'a']++;

            if (r - l + 1 == k)
            {

                for (int i = l;i <= r;i++)
                {
                    if (hash_s1[s2[i] - 'a'] != hash_s2[s2[i] - 'a'])
                    {
                        flag = false;
                    }
                }

                if (flag)
                {
                    return true;
                }


                hash_s2[s2[l] - 'a']--;
                l++;
                flag = true;

            }
        }



        return false;

    }
};

//删除一个元素后的最长字符串

class Solution {
public:
    int longestSubarray(vector<int>& nums) {

        int n = nums.size();
        int ans = 0;
        int count_one = 0;
        int  count_zero = 0;

        for (int r = 0, l = 0;l < n, r < n;r++)
        {
            if (nums[r] == 1)
            {
                count_one++;
            }
            else
            {
                count_zero++;
            }

            if (count_zero >= 2)
            {
                ans = max(count_one, ans);

                if (nums[l] == 0)
                {
                    count_zero--;
                }
                else
                {
                    count_one--;
                }
                l++;
            }


        }


        ans = max(ans, count_one);

        return ans == n ? ans - 1 : ans;







    }
};

//k个重复元素的最长子数组
class Solution {
public:
    int maxSubarrayLength(vector<int>& nums, int k) {

        int n = nums.size();
        unordered_map<int, int>hash;
        int ans = 0;
        int l = 0, r = 0;
        for (l = 0, r = 0;r < n;r++)
        {
            if (++hash[nums[r]] > k)
            {
                ans = max(ans, r - l);
                while (hash[nums[r]] > k)
                {
                    --hash[nums[l++]];
                }
            }
        }

        return  ans = max(ans, r - l);


    }
};

//不超过限制值的子数组最大长度
class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {

        multiset<int>st;
        int left = 0, right = 0;
        int res = 0;

        while (right < nums.size())
        {
            st.insert(nums[right]);
            while (*st.rbegin() - *st.begin() > limit)
            {
                st.erase(st.find(nums[left]));
                left++;
            }

            res = max(res, right - left + 1);
            right++;
        }

        return res;


    }
};


//删除链表的重复元素
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {

        if (!head || !head->next)
        {
            return head;
        }

        if (head->val != head->next->val)
        {
            head->next = deleteDuplicates(head->next);
        }
        else
        {
            ListNode* move = head->next;
            while (move && head->val == move->val)
            {
                move = move->next;
            }
            return deleteDuplicates(move);
        }

        return head;


    }
};

//最大字符串匹配数目
class Solution {
public:
    int maximumNumberOfStringPairs(vector<string>& words) {

        int len = words.size();
        int n = 0;
        int arr[26][26] = { 0 };


        for (int i = 0;i < len;i++)
        {
            arr[words[i][0] - 'a'][words[i][1] - 'a']++;
        }

        for (int i = 0;i < len;i++)
        {
            if (arr[words[i][0] - 'a'][words[i][1] - 'a'] == arr[words[i][1] - 'a'][words[i][0] - 'a'] && words[i][0] != words[i][1])
            {
                n += arr[words[i][0] - 'a'][words[i][1] - 'a'];
                arr[words[i][0] - 'a'][words[i][1] - 'a'] = arr[words[i][1] - 'a'][words[i][0] - 'a'] = 0;
            }

        }

        return n;


    }
};

//统计完全子数组的个数
class Solution {
public:
    int countCompleteSubarrays(vector<int>& nums) {

        int n = nums.size();
        unordered_map<int, int>hash;
        for (int i = 0;i < n;i++)
        {
            hash[nums[i]]++;
        }

        int sum = hash.size();//统计桶的个数
        cout << sum << endl;

        hash.clear();
        int count = 0;

        for (int l = 0, r = 0;r < n;r++)
        {
            hash[nums[r]]++;
            while (hash.size() == sum)
            {
                int x = nums[l++];
                if (--hash[x] == 0)
                {
                    hash.erase(x);
                }
            }

            count += l;

        }

        return count;

    }
};

//在排序数组中查找元素的第一个位置和最后一个位置
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {



        vector<int>pos;
        if (nums.size() == 0)
        {
            pos.push_back(-1);
            pos.push_back(-1);
            return pos;
        }

        int left = 0;
        int right = nums.size() - 1;
        int mid = 0;
        while (left < right)
        {
            mid = (right + left) >> 1;
            if (nums[mid] >= target)
            {
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
        }

        if (nums[right] == target)
        {
            pos.push_back(right);
            right = nums.size() - 1;
            while (left < right)
            {
                mid = (right + left + 1) >> 1;
                if (nums[mid] <= target)
                {
                    left = mid;
                }
                else
                {
                    right = mid - 1;
                }
            }

            if (nums[left] == target)
            {
                pos.push_back(left);
            }
            else
            {
                pos.push_back(-1);
            }
        }

        else
        {
            pos.push_back(-1);
            pos.push_back(-1);
        }


        return pos;

    }
};
//分割数组的最大值
class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        long long l = nums[0], h = 0;
        for (auto n : nums)
        {
            h += n;
            if (n > l) l = n;
        }

        while (l < h)
        {
            long long mid = (l + h) / 2;
            long long temp = 0;
            int cnt = 1;//统计组数

            for (auto i : nums)
            {
                temp += i;
                if (temp > mid)
                {
                    temp = i;
                    ++cnt;
                }
            }

            if (cnt > m)
            {
                l = mid + 1;
            }
            else
            {
                h = mid;
            }
        }


        return l;

    }
};


//k倍区间的个数
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;

const int N = 1e5 + 10;
long long  arr[N], cnt[N];
long long s[N];
int K, n;

int main()
{
    scanf("%d%d", &n, &K);
    for (int i = 1;i <= n;i++)
    {
        scanf("%d", &arr[i]);
        s[i] = s[i - 1] + arr[i];
    }

    long long count = 0;
    cnt[0] = 1;

    for (int i = 1;i <= n;i++)
    {
        count += cnt[s[i] % K];
        cnt[s[i] % K]++;
    }


    cout << count << endl;

    return 0;

}
//排序子序列

#include <iostream>
#include<vector>
using namespace std;

int main() {

    int n = 0;
    cin >> n;
    vector<int>a;
    a.resize(n + 1);

    for (int i = 0;i < n;i++)
    {
        cin >> a[i];
    }

    int i = 0;
    int count = 0;

    while (i < n)
    {
        if (a[i] < a[i + 1])
        {
            while (i < n && a[i] < a[i + 1])
            {
                i++;
            }
            count++;
            i++;
        }

        else if (a[i] == a[i + 1])
        {
            i++;
        }
        else
        {
            while (i<n && a[i]>a[i + 1])
            {
                i++;
            }
            count++;
            i++;

        }
    }



    cout << count << endl;
    return 0;


}

// 计算 K 置位下标对应元素的和
class Solution {
public:
    bool check(int pos, int k)
    {
        int count = 0;
        for (int i = 0;i < 32;i++)
        {
            if ((pos >> i) & 1) count++;
        }

        return count == k;
    }

    int sumIndicesWithKSetBits(vector<int>& nums, int k) {

        int n = nums.size();
        int sum = 0;
        for (int i = 0;i < n;i++)
        {
            if (check(i, k))
            {
                sum += nums[i];
            }

        }

        return sum;
    }
};

//除自身以外数组的乘积
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {

        int n = nums.size();
        vector<int>back(n + 1);
        back[n] = 1;
        vector<int>front(n + 1);
        front[0] = 1;
        vector<int>ans(n);

        for (int i = 0;i < n;i++)
        {
            front[i + 1] = front[i] * nums[i];
        }

        for (int j = n - 1;j >= 0;j--)
        {
            back[j] = nums[j] * back[j + 1];
        }


        for (int i = 0;i < n;i++)
        {
            ans[i] = front[i] * back[i + 1];
        }


        return ans;


    }
};

//和为k的子数组个数
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {

        int sum = 0;
        int ret = 0;
        unordered_map<int, int>hash;
        hash[0] = 1;
        for (auto x : nums)
        {
            sum += x;
            if (hash.count(sum - k))
            {
                ret += hash[sum - k];
            }
            hash[sum]++;
        }

        return ret;

    }
};

//感冒的蚂蚁数量
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 55;
int arr[N];

int main()
{
    int n = 0;
    cin >> n;
    for (int i = 0;i < n;i++)
    {
        cin >> arr[i];
    }

    int left = 0;//表示左边向右走的
    int right = 0;//表示右边向左走的

    for (int i = 0;i < n;i++)
    {
        if (abs(arr[i]) > abs(arr[0]) && arr[i] < 0) right++;
        if (abs(arr[i]) < abs(arr[0]) && arr[i] > 0) left++;
    }

    if ((arr[0] > 0 && right == 0) || (arr[0] < 0 && left == 0)) cout << 1 << endl;
    else cout << right + left + 1 << endl;

    return 0;

}
//连续数组
class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        int len = 0;
        unordered_map<int, int>hash;
        hash[0] = -1;

        for (int i = 0;i < n;i++)
        {
            if (nums[i] == 0)
            {
                sum += -1;
            }
            else
            {
                sum += 1;
            }

            if (hash.count(sum))
            {
                len = max(len, i - hash[sum]);
            }

            if (!hash.count(sum))
            {
                hash[sum] = i;
            }

        }

        return len;

    }
};
//只出现一次的两个数
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {

        unsigned res = 0;
        int n = nums.size();

        for (int i = 0;i < n;i++)
        {
            res ^= nums[i];
        }

        unsigned  int lowbit = res & (-res);//提取出最右侧的1

        vector<int>ans(2);

        for (int i = 0;i < n;i++)//将nums根据最右侧的1进行分组
        {
            ans[(nums[i] & lowbit) != 0] ^= nums[i];
        }

        return ans;



    }
};

//递增三元组
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 1e5 + 10;
#define INF 1e5

int A[N], B[N], C[N], cs[N], as[N], cnt[N], s[N];


int main()
{
    int n = 0;
    cin >> n;

    for (int i = 0;i < n;i++) cin >> A[i], A[i]++;
    for (int i = 0;i < n;i++) cin >> B[i], B[i]++;
    for (int i = 0;i < n;i++) cin >> C[i], C[i]++;

    for (int i = 0;i < n;i++) cnt[A[i]]++;
    for (int i = 1;i < N;i++)  s[i] = s[i - 1] + cnt[i];
    for (int i = 0;i < n;i++)  as[i] = s[B[i] - 1];

    memset(cnt, 0, sizeof cnt), memset(s, 0, sizeof s);

    for (int i = 0;i < n;i++) cnt[C[i]]++;
    for (int i = 1;i < N;i++)  s[i] = s[i - 1] + cnt[i];
    for (int i = 0;i < n;i++)  cs[i] = s[N - 1] - s[B[i]];

    long long res = 0;

    for (int i = 0;i < n;i++) res += (long long)as[i] * cs[i];

    cout << res << endl;



    return 0;
}
//外卖的优先级

include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n, m, T;
int score[N], last[N];
bool st[N];

PII order[N];

int main()
{
    scanf("%d%d%d", &n, &m, &T);
    for (int i = 0; i < m; i++) scanf("%d%d", &order[i].x, &order[i].y);
    sort(order, order + m);

    for (int i = 0; i < m;)
    {
        int j = i;
        while (j < m && order[j] == order[i]) j++;
        int t = order[i].x, id = order[i].y, cnt = j - i;
        i = j;

        score[id] -= t - last[id] - 1;
        if (score[id] < 0) score[id] = 0;
        if (score[id] <= 3) st[id] = false; // 以上处理的是t时刻之前的信息

        score[id] += cnt * 2;
        if (score[id] > 5) st[id] = true;

        last[id] = t;
    }

    for (int i = 1; i <= n; i++)
        if (last[i] < T)
        {
            score[i] -= T - last[i];
            if (score[i] <= 3) st[i] = false;
        }

    int res = 0;
    for (int i = 1; i <= n; i++) res += st[i];

    printf("%d\n", res);

    return 0;
}
//Z字型变换
class Solution {
public:
    string convert(string s, int numRows) {

        int n = s.size();
        if (n == 1 || numRows == 1) return s;

        string str;

        for (int i = 0;i < numRows;i++)
        {
            if (i == 0 || i == numRows - 1)
            {
                int j = i;
                while (j < n)
                {
                    str += s[j];
                    j += 2 * numRows - 2;
                }
            }
            else
            {
                int a = i, b = 2 * numRows - 2 - i;
                while (a < n)
                {
                    if (a < n)str += s[a];
                    if (b < n)str += s[b];
                    a += 2 * numRows - 2, b += 2 * numRows - 2;
                }
            }

        }

        return str;

    }
};
//外观数列
class Solution {
public:
    string countAndSay(int n) {

        string desc;
        string str = "1";

        while (--n)
        {
            int len = str.size();
            int count = 0;
            for (int l = 0, r = 0;r <= len;r++)
            {
                if (r != len && str[r] == str[l])
                {
                    count++;
                }
                else
                {
                    if (count != 0) desc += to_string(count);
                    desc += str[l];
                    while (str[l] != str[r])
                    {
                        l++;
                    }
                    count = 1;
                }
            }
            str = desc;
            desc.clear();

        }


        return str;

    }
};
 //数青蛙
class Solution {
public:
    int minNumberOfFrogs(string  s) {

        char arr[5] = { 'c','r','o','a','k' };

        unordered_map<char, int>hash;

        int n = s.size();

        for (int i = 0;i < n;i++)
        {
            if (s[i] == 'c')
            {
                if (hash['k']) hash['k']--;
                hash['c']++;
            }
            else if (s[i] == 'r')
            {
                if (!hash['c']) return -1;
                else
                {
                    hash['c']--;
                    hash['r']++;
                }
            }
            else if (s[i] == 'o')
            {
                if (!hash['r']) return -1;
                else
                {
                    hash['r']--;
                    hash['o']++;
                }
            }
            else if (s[i] == 'a')
            {
                if (!hash['o']) return -1;
                else
                {
                    hash['o']--;
                    hash['a']++;
                }
            }
            else if (s[i] == 'k')
            {
                if (!hash['a']) return -1;
                else
                {
                    hash['a']--;
                    hash['k']++;
                }
            }
        }

        for (int i = 0;i < 4;i++)
        {
            if (hash[arr[i]]) return -1;
        }
        return hash['k'];

    }
};
//颜色分类
class Solution {
public:

    void meger_sort(int l, int r, vector<int>& nums, vector<int>& temp)
    {
        if (l >= r) return;

        int mid = (l + r) >> 1;

        meger_sort(l, mid, nums, temp), meger_sort(mid + 1, r, nums, temp);

        int i = l, j = mid + 1, k = 0;

        while (i <= mid && j <= r)
        {
            if (nums[i] < nums[j])
            {
                temp[k++] = nums[i++];
            }
            else
            {
                temp[k++] = nums[j++];
            }
        }

        while (i <= mid)
        {
            temp[k++] = nums[i++];
        }

        while (j <= r)
        {
            temp[k++] = nums[j++];
        }

        for (int i = l, k = 0;i <= r;i++)
        {
            nums[i] = temp[k++];
        }


    }

    void sortColors(vector<int>& nums) {

        int l = 0;
        int r = nums.size() - 1;
        vector<int>temp(310);
        meger_sort(l, r, nums, temp);

    }
};

//快速选择排序
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {

        srand(time(0));//随机数种子
        return qsort(nums, 0, nums.size() - 1, k);

    }

    int qsort(vector<int>& nums, int l, int r, int k)
    {
        if (l == r) return nums[l];

        int key = Getrandom(nums, l, r);

        int left = l - 1, right = r + 1, i = l;

        while (i < right)
        {
            if (nums[i] < key) swap(nums[++left], nums[i++]);
            else if (nums[i] == key) i++;
            else  swap(nums[--right], nums[i]);
        }

        //分组
        int b = right - left - 1, c = r - right + 1;
        if (c >= k) return qsort(nums, right, r, k);
        else if (b + c >= k) return key;
        else return qsort(nums, l, left, k - b - c);


    }


    int Getrandom(vector<int>& nums, int left, int right)
    {
        return  nums[rand() % (right - left + 1) + left];
    }

};

//最小的前k个数字
class Solution {
public:
    vector<int> inventoryManagement(vector<int>& nums, int cnt) {

        srand(0);
        qsort(nums, 0, nums.size() - 1, cnt);
        return { nums.begin(),nums.begin() + cnt };
    }

    void qsort(vector<int>& nums, int l, int r, int k)
    {
        if (l >= r) return;
        int key = Getrandom(nums, l, r);

        int left = l - 1, right = r + 1, i = l;

        while (i < right)
        {
            if (nums[i] < key) swap(nums[++left], nums[i++]);
            else if (nums[i] == key) i++;
            else swap(nums[--right], nums[i]);
        }

        int a = left - l + 1, b = right - left - 1;

        if (a >= k) qsort(nums, l, left, k);
        else if (a + b >= k) return;
        else qsort(nums, right, r, k - a - b);
    }

    int Getrandom(vector<int>& nums, int left, int right)
    {
        return nums[rand() % (right - left + 1) + left];
    }
};

//逆序对的数量
class Solution {
public:
    int res = 0;
    int temp[50000];

    void merge_sort(vector<int>& record, int l, int r)
    {
        if (l >= r) return;

        int mid = (l + r) / 2;
        merge_sort(record, l, mid), merge_sort(record, mid + 1, r);

        int i = l, j = mid + 1, k = 0;


        while (i <= mid && j <= r)
        {
            if (record[i] <= record[j])
            {
                temp[k++] = record[i++];
            }
            else
            {
                temp[k++] = record[j++];
                res += mid - i + 1;

            }
        }

        while (i <= mid) temp[k++] = record[i++];
        while (j <= r) temp[k++] = record[j++];

        for (int i = l, j = 0;i <= r;i++, j++)
        {

            record[i] = temp[j];
        }

    }

    int reversePairs(vector<int>& record) {

        merge_sort(record, 0, record.size() - 1);

        for (int i = 0;i < record.size();i++)
        {
            cout << record[i] << endl;
        }

        return res;

    }
};

//层序遍历II
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>>ret;
        vector<int>v;
        queue<TreeNode*>q;
        int i = 0;
        int level = 1, count = 0;

        if (root != nullptr)
        {
            q.push(root);
        }

        while (!q.empty())
        {
            while (level)
            {
                TreeNode* front = q.front();
                q.pop();
                v.push_back(front->val);
                level--;

                if (front->left)
                {
                    q.push(front->left);
                    count++;
                }

                if (front->right)
                {
                    q.push(front->right);
                    count++;
                }
            }

            ret.push_back(v);
            v.clear();
            level = count;
            count = 0;


        }

        reverse(ret.begin(), ret.end());

        return ret;

    }
};

//

int n = s.size();
int mid = n / 2;

int ret = 0;
for (int i = 0;i < n;i++)
{
    if (s[i] == 'a' || s[i] == 'A' || s[i] == 'e' || s[i] == 'E'
        || s[i] == 'i' || s[i] == 'I' || s[i] == 'o' || s[i] == 'O'
        || s[i] == 'u' || s[i] == 'U')
    {
        if (i >= mid) ret--;
        else ret++;
    }
}

return ret == 0;

//字符串解码

class Solution {
public:
    string decodeString(string s) {

        int num = 0;
        string res;
        stack<string> strs;
        stack<int>nums;

        for (int i = 0;i < s.size();i++)
        {
            if (s[i] >= '0' && s[i] <= '9')
            {
                num = num * 10 + (s[i] - '0');
            }

            else if (s[i] >= 'a' && s[i] <= 'z')
            {
                res += s[i];
            }

            else if (s[i] == '[')//开始入栈
            {
                strs.push(res);
                res = "";
                nums.push(num);
                num = 0;
            }
            else//开始出栈
            {
                int times = nums.top();
                nums.pop();
                for (int i = 0;i < times;i++)
                {
                    strs.top() += res;
                }

                res = strs.top();
                strs.pop();

            }
        }

        return res;


    }
};

//迷宫中离入口最近的出口
class Solution {
public:
    int dist[100][100];
    queue<pair<int, int>>q;
    int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
    int step = 0;

    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int m = maze.size(), n = maze[0].size();
        memset(dist, -1, sizeof dist);

        int startx = entrance[0], starty = entrance[1];
        dist[startx][starty] = 0;
        q.push({ startx,starty });

        while (q.size())
        {


            pair<int, int>front = q.front();
            q.pop();

            for (int i = 0;i < 4;i++)
            {
                int x = front.first + dx[i], y = front.second + dy[i];
                if (x < 0 || x >= m || y < 0 || y >= n) continue;
                else if (maze[x][y] == '+') continue;
                else if (dist[x][y] != -1)continue;


                dist[x][y] = dist[front.first][front.second] + 1;
                q.push({ x,y });
                if (x == 0 || x == m - 1 || y == 0 || y == n - 1) return dist[x][y];
            }




        }

        return -1;


    }
};

//单词接龙
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {

        unordered_set<string>hash(wordList.begin(), wordList.end());
        unordered_set<string>used;

        queue<string>q;
        q.push(beginWord);
        used.insert(beginWord);

        int step = 1;
        while (q.size())
        {
            step++;
            int size = q.size();
            for (int i = 0;i < size;i++)
            {
                string front = q.front();
                q.pop();

                for (int j = 0;j < front.size();j++)
                {
                    string temp = front;
                    for (int k = 0;k < 26;k++)
                    {
                        temp[j] = 'a' + k;
                        if (hash.count(temp) && (!used.count(temp)))
                        {
                            q.push(temp);
                            used.insert(temp);
                            if (temp == endWord) return step;
                        }

                    }
                }
            }
        }

        return 0;

    }
};

//高尔夫砍树
class Solution {
public:

    int m, n;
    int bfs(vector<vector<int>>& forest, int sx, int sy, int destx, int desty)
    {

        if (sx == destx && sy == desty) return 0;

        queue<pair<int, int>>q; bool used[m][n];

        memset(used, false, sizeof used);

        q.push({ sx,sy });

        used[sx][sy] = true;

        int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };

        int step = 0;
        while (q.size())
        {

            int size = q.size();
            step++;
            for (int i = 0;i < size;i++)
            {
                pair<int, int>front = q.front();
                q.pop();
                for (int j = 0;j < 4;j++)
                {
                    int x = front.first + dx[j], y = front.second + dy[j];
                    if ((x >= 0 && x < m && y >= 0 && y < n) && !used[x][y] && forest[x][y] != 0)
                    {
                        q.push({ x,y });
                        used[x][y] = true;
                        forest[x][y] = 1;
                        if (x == destx && y == desty) return step;
                    }

                }
            }

        }
        return -1;


    }



    int cutOffTree(vector<vector<int>>& forest) {

        m = forest.size(), n = forest[0].size();
        vector<pair<int, int>>hash;

        for (int i = 0;i < m;i++)
        {
            for (int j = 0;j < n;j++)
            {
                if (forest[i][j] > 1) hash.push_back({ i,j });
            }
        }


        sort(hash.begin(), hash.end(), [&](const pair<int, int>p1, const pair<int, int>p2)
            {
                return forest[p1.first][p1.second] < forest[p2.first][p2.second];
            });


        int ret = 0;
        int startx = 0, starty = 0;


        for (int i = 0;i < hash.size();i++)
        {
            int x = hash[i].first, y = hash[i].second;
            int step = bfs(forest, startx, starty, x, y);

            if (step == -1) return -1;
            ret += step;
            startx = x, starty = y;
        }



        return ret;


    }




};

//0 1矩阵
class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {

        int m = mat.size(), n = mat[0].size();

        vector<vector<int>>dest(m, vector<int>(n, -1));

        queue<pair<int, int>>q;

        for (int i = 0;i < m;i++)
        {
            for (int j = 0;j < n;j++)
            {
                if (mat[i][j] == 0)//将所有的起点加入到队列中
                {
                    q.push({ i,j });
                    dest[i][j] = 0;
                }
            }
        }

        int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
        while (q.size())
        {
            pair<int, int>pos = q.front();
            q.pop();

            for (int i = 0;i < 4;i++)
            {
                int x = pos.first + dx[i], y = pos.second + dy[i];
                if (x < 0 || x >= m || y < 0 || y >= n || dest[x][y] != -1) continue;

                dest[x][y] = dest[pos.first][pos.second] + 1;
                q.push({ x,y });
            }
        }

        return dest;

    }
};

//地图中的最高点
class Solution {
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {

        int m = isWater.size(), n = isWater[0].size();

        vector<vector<int>>dist(m, vector<int>(n, 0));

        queue<pair<int, int>>q;
        for (int i = 0;i < m;i++)
        {
            for (int j = 0;j < n;j++)
            {
                if (isWater[i][j] == 1)
                {
                    q.push({ i,j });
                }
            }
        }


        int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
        while (q.size())
        {
            pair<int, int>front = q.front();
            q.pop();

            for (int i = 0;i < 4;i++)
            {
                int x = front.first + dx[i], y = front.second + dy[i];
                if (x < 0 || x >= m || y < 0 || y >= n || dist[x][y] != 0 || isWater[x][y] == 1) continue;
                dist[x][y] = dist[front.first][front.second] + 1;
                q.push({ x,y });
            }

        }

        return dist;

    }
};

//火星字典
class Solution {
    unordered_map<char, unordered_set<char>> edges; // 邻接表来存储图
    unordered_map<char, int> in;                    // 统计⼊度
    bool cheak;                                     // 处理边界情况
public:
    string alienOrder(vector<string>& words) {
        // 1. 建图 + 初始化⼊度哈希表
        for (auto& s : words) {
            for (auto ch : s) {
                in[ch] = 0;
            }
        }
        int n = words.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                add(words[i], words[j]);
                if (cheak)
                    return "";
            }
        }
        // 2. 拓扑排序
        queue<char> q;
        for (auto& [a, b] : in) {
            if (b == 0)
                q.push(a);
        }
        string ret;
        while (q.size()) {
            char t = q.front();
            q.pop();
            ret += t;
            for (char ch : edges[t]) {
                if (--in[ch] == 0)
                    q.push(ch);
            }
        }
        // 3. 判断
        for (auto& [a, b] : in)
            if (b != 0)
                return "";
        return ret;
    }
    void add(string& s1, string& s2) {
        int n = min(s1.size(), s2.size());
        int i = 0;
        for (; i < n; i++) {
            if (s1[i] != s2[i]) {
                char a = s1[i], b = s2[i]; // a -> b
                if (!edges.count(a) || !edges[a].count(b)) {
                    edges[a].insert(b);
                    in[b]++;
                }
                break;
            }
        }
        if (i == s2.size() && i < s1.size())
            cheak = true;
    }
};
//红与黑
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;

const int H = 20, W = 20;

char arr[H][W];


int main()
{
    while (1)
    {
        int w, h;
        scanf("%d%d", &w, &h);
        if (w == 0 && h == 0) break;

        for (int i = 0;i < h;i++)
        {
            scanf("%s", arr[i]);
        }

        queue<pair<int, int>>q;
        for (int i = 0;i < h;i++)
        {
            for (int j = 0;j < w;j++)
            {
                if (arr[i][j] == '@')
                {
                    q.push({ i,j });
                }
            }
        }


        int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
        int used[h][w];
        memset(used, 0, sizeof used);
        int sum = 0;
        while (q.size())
        {
            pair<int, int>front = q.front();
            q.pop();
            for (int i = 0;i < 4;i++)
            {
                int x = front.first + dx[i], y = front.second + dy[i];
                if (x < 0 || x >= h || y < 0 || y >= w || arr[x][y] == '#' || used[x][y])continue;

                sum++;
                used[x][y] = 1;
                q.push({ x,y });

            }
        }

        if (sum == 0) sum++;
        cout << sum << endl;

    }
    return 0;
}

//合并k个升序链表
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {

        vector<int>num;
        for (int i = 0;i < lists.size();i++)
        {
            ListNode* cur = lists[i];
            while (cur)
            {
                num.push_back(cur->val);
                cur = cur->next;
            }
        }

        sort(num.begin(), num.end());

        ListNode* head = nullptr;
        ListNode* tail = nullptr;

        for (int i = 0;i < num.size();i++)
        {
            int val = num[i];
            if (head == nullptr)
            {
                head = new ListNode(val);
                tail = head;
            }
            else
            {
                ListNode* newnode = new ListNode(val);
                tail->next = newnode;
                tail = tail->next;
            }
        }

        return head;


    }
};

//等差数列
#include<iostream>
#include<cstdio>
#include<cstring>
#include<climits>
#include<algorithm>
#include<cmath>
using namespace std;

int getMin(int a, int b)
{
    return b ? getMin(b, a % b) : a;
}

const int N = 100010;
int arr[N];
int n;
int main()
{
    scanf("%d", &n);
    for (int i = 0;i < n;i++)
    {
        cin >> arr[i];
    }
    sort(arr, arr + n);
    int Mingap = 0;
    for (int j = 1;j < n;j++)
    {
        Mingap = getMin(Mingap, arr[j] - arr[0]);

    }

    if (Mingap) cout << (arr[n - 1] - arr[0]) / Mingap + 1 << endl;
    else cout << n << endl;
    return 0;
}

//最长公共子序列
class Solution {
public:

    int longestCommonSubsequence(string text1, string text2) {



        int n1 = text1.size();
        int n2 = text2.size();
        text1 = ' ' + text1;
        text2 = ' ' + text2;
        vector<vector<int>>dp(n1 + 1, vector<int>(n2 + 1));




        for (int i = 1;i <= n1;i++)
        {
            for (int j = 1;j <= n2;j++)
            {
                if (text1[i] == text2[j])
                {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else
                {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[n1][n2];


    }
};

//反转k个节点
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {

        if (head == nullptr) return nullptr;

        ListNode* lr = head;

        ListNode* newHead = nullptr;ListNode* tail = nullptr;

        vector<int>arr;

        while (lr)
        {
            int temp = k;
            while (temp-- && lr)
            {

                arr.push_back(lr->val);
                lr = lr->next;

            }



            int size = arr.size();
            if (size + 1 <= k) break;



            while (size)
            {
                if (tail == nullptr)
                {

                    newHead = new ListNode(arr[size - 1]);
                    tail = newHead;
                }
                else
                {
                    tail->next = new ListNode(arr[size - 1]);
                    tail = tail->next;
                }
                size--;
            }

            arr.clear();
        }

        for (auto e : arr)
        {
            tail->next = new ListNode(e);
            tail = tail->next;
        }

        return newHead;



    }
};

//两数之和
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {

        vector<int>arr;
        unordered_map<int, int>hash;
        for (int i = 0;i < nums.size();i++)
        {
            hash[nums[i]] = i;
        }

        for (int i = 0;i < nums.size();i++)
        {
            int n = target - nums[i];
            if (hash.count(n) && hash[n] != i)
            {
                arr.push_back(i);
                arr.push_back(hash[n]);
                break;
            }
        }

        return arr;

    }
};

//编辑距离
class Solution {
public:
    int minDistance(string word1, string word2) {

        int m = word1.size(), n = word2.size();

        vector<vector<int>>dp(m + 1, vector<int>(n + 1));

        for (int i = 0;i <= m;i++)
        {
            dp[i][0] = i;
        }
        for (int j = 0;j <= n;j++)
        {
            dp[0][j] = j;
        }

        for (int i = 1;i <= m;i++)
        {
            for (int j = 1;j <= n;j++)
            {
                if (word1[i - 1] == word2[j - 1])
                {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else
                {
                    dp[i][j] = min({ dp[i - 1][j - 1],dp[i - 1][j],dp[i][j - 1] }) + 1;
                }
            }
        }

        return dp[m][n];

    }
};

//光标的位置

#include <iostream>
#include<vector>
using namespace std;

int main() {

    int n;
    string cmd;
    while (cin >> n >> cmd)
    {
        int first = 1, num = 1;
        if (n <= 4)
        {
            for (int i = 0;i < cmd.size();i++)//解析命令
            {
                if (num == 1 && cmd[i] == 'U')
                {
                    num = n;
                }
                else if (num == n && cmd[i] == 'D')
                {
                    num = 1;
                }
                else if (cmd[i] == 'U')
                {
                    num--;
                }
                else {
                    num++;
                }
            }

            for (int i = 1;i <= n;i++)
            {
                cout << i << " ";
            }
            cout << endl;
            cout << num;
        }
        else
        {
            for (int i = 0;i < cmd.size();i++)
            {
                if (first == 1 && num == 1 && cmd[i] == 'U')//在第一页第一行并且要向上
                {
                    first = n - 3;
                    num = n;
                }
                else if (first == n - 3 && num == n && cmd[i] == 'D')//在最后一页，first是第一行，并且要向下翻
                {
                    first = num = 1;
                }
                else if (first == num && cmd[i] == 'U')
                {
                    num--;
                    first = --first;
                }
                else if (first == num - 3 && cmd[i] == 'D')
                {
                    num++;
                    first = ++first;
                }
                else if (cmd[i] == 'D')
                {
                    num++;
                }
                else {
                    num--;
                }
            }

            for (int i = 0;i < 4;i++)
            {
                cout << first + i << " ";
            }

            cout << endl;

            cout << num;

        }
    }

    return 0;

}


//走方格
#include<iostream>
#include<vector>
using namespace std;

int n, m;
int main()
{
    cin >> n >> m;

    vector<vector<int>>dp(n + 1, vector<int>(m + 1));

    for (int i = 1;i <= n;i++)
    {
        dp[i][1] = 1;
    }

    for (int j = 1;j <= m;j++)
    {
        dp[1][j] = 1;
    }



    for (int i = 2;i <= n;i++)
    {
        for (int j = 2;j <= m;j++)
        {
            int x1 = i, y1 = j - 1;
            int x2 = i - 1, y2 = j;

            if (!(x1 % 2 == 0 && y1 % 2 == 0))
            {
                dp[i][j] += dp[x1][y1];
            }

            if (!(x2 % 2 == 0 && y2 % 2 == 0))
            {
                dp[i][j] += dp[x2][y2];
            }


            if (i % 2 == 0 && j % 2 == 0)
            {
                dp[i][j] = 0;
            }

        }
    }



    cout << dp[n][m] << endl;


    return 0;
}

//整数拼接
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
using ll = long long;

int m, n;
const int N = 100010;
int arr[N], s[11][N];//长度和余数

int main()
{
    cin >> n >> m;

    for (int i = 0;i < n;i++)
    {
        cin >> arr[i];
    }

    for (int i = 0;i < n;i++)
    {
        int t = arr[i] % m;
        for (int j = 0;j < 11;j++)//初始化长度和余数对应的二维数组
        {
            s[j][t]++;
            t = t * 10 % m;
        }
    }

    ll res = 0;//代表结果
    for (int i = 0;i < n;i++)
    {
        int t = arr[i] % m;//计算余数
        int len = to_string(arr[i]).size();//计算长度
        res += s[len][(m - t) % m];

        ll r = t;//判重
        while (len--) r = r * 10 % m;
        if (r == (m - t) % m) res--;
    }


    cout << res << endl;
    return 0;
}
//砝码称重
#include<iostream>
using namespace std;

const int N = 200020;
int w[N];
bool dp[110][N];//dp数组
int m = 0;//统计总重量
int n;
int b = N / 2;//偏移量，因为重量的范围会在-m~m


int main()
{

    cin >> n;
    for (int i = 1;i <= n;i++)
    {
        cin >> w[i];//输入数据并且统计总和
        m += w[i];
    }


    dp[0][b] = true;

    for (int i = 1;i <= n;i++)//下标的范围
    {
        for (int j = -m;j <= m;j++)//重量的范围
        {
            //分情况讨论：
            //1，在i下标啥也不拿
            dp[i][j + b] = dp[i - 1][j + b];
            //2，拿了重量到j
            if (j - w[i] >= -m)
            {
                dp[i][j + b] |= dp[i - 1][j - w[i] + b];
            }
            //3,减去重量到j
            if (j + w[i] <= m)
            {
                dp[i][j + b] |= dp[i - 1][j + w[i] + b];
            }
        }
    }

    int res = 0;

    for (int j = 1;j <= m;j++)
    {
        if (dp[n][j + b]) res++;
    }

    cout << res << endl;

    return 0;
}

//深度优先搜索
#include<iostream>
#include<vector>
using namespace std;
const int N = 20;
int arr[N];
int num, ret;
vector<vector<int>>res;
void dfs(int u, int sum)
{
    if (sum > num)//剪枝操作
    {
        return;
    }

    if (u > 9)
    {
        if (sum == num)
        {
            vector<int>v;
            for (int i = 0;i < 10;i++)
            {
                v.push_back(arr[i]);
            }
            ret++;
            res.push_back(v);
        }

        return;
    }

    for (int i = 1;i <= 3;i++)
    {
        arr[u] = i;
        dfs(u + 1, sum + i);
        arr[u] = 0;
    }
}

int main()
{

    cin >> num;
    dfs(0, 0);//深度优先搜索
    cout << ret << endl;
    for (int i = 0;i < ret;i++)
    {
        for (int j = 0;j < 10;j++)
        {
            cout << res[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

//合的质数个数
//养成好习惯，包上常用头文件
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

//根据题目要求开数组
const int N = 30;

//arr数组用来读入数据
int arr[N];

//st数组用来存放数据
int st[N];

int n, k;

//记录素数个数并返回
int res = 0;

//判断是否是素数
bool is_prime(int sum)
{
    if (sum < 2)
    {
        return false;
    }
    for (int i = 2; i <= sum / i; i++)
    {
        if (sum % i == 0)
        {
            return false;
        }
    }
    return true;
}

void dfs(int u, int start)
{
    //如果：(已经存放的数 + 剩余可选的数 < 需要的数量)就剪枝
    if ((u - 1) + (n - start + 1) < k)
    {
        return;
    }

    if (u > k)
    {
        //求和
        int sum = 0;
        for (int i = 1; i <= k; i++)
        {
            sum += st[i];
        }

        //判断
        if (is_prime(sum))
        {
            res++;
        }
        return;
    }

    for (int i = start; i <= n; i++)
    {
        st[u] = arr[i];
        dfs(u + 1, i + 1);
        st[i] = 0;
    }
}

int main()
{
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &arr[i]);
    }
    dfs(1, 1);
    printf("%d\n", res);
    return 0;
}

//找出感染源

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int N = 510;

int n, m, a, b;
pair<int, int>mark_1[N];
pair<int, int>mark_2[N];
int dist[N][N];
queue<pair<int, int>>q;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

void bfs()
{


    while (q.size())
    {
        pair<int, int>front = q.front();
        q.pop();

        for (int i = 0;i < 4;i++)
        {
            int x = front.first + dx[i];
            int y = front.second + dy[i];

            if (x < 1 || x > n || y < 1 || y > m)
            {
                continue;
            }
            else if (dist[x][y] >= 0)
            {
                continue;
            }

            dist[x][y] = dist[front.first][front.second] + 1;
            q.push({ x,y });
            //  cout << dist[x][y] << endl;
        }

    }

}


int main()
{
    scanf("%d %d %d %d", &n, &m, &a, &b);
    //初始化状态数组
    memset(dist, -1, sizeof(dist));
    for (int i = 0; i < a; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);

        //现将所以瘟疫源都入队，就能实现几个位置同时搜索
        q.push({ x,y });
        dist[x][y] = 0;
    }

    bfs();

    //根据题目输入顺序输出领主
    for (int i = 0; i < b; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        printf("%d\n", dist[x][y]);
    }
    return 0;

}
 
//填涂颜色
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;


const int N = 50;
int n;
int board[N][N];
int mark[N][N];
queue<pair<int, int>>q;
int dx[] = { 1,0,-1,0 }, dy[] = { 0,-1,0,1 };

void bfs()
{
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        for (int i = 0;i < 4;i++)
        {
            int x = t.first + dx[i];
            int y = t.second + dy[i];

            if (x >= n || x < 0 || y >= n || y < 0)
            {
                continue;
            }
            else if (mark[x][y] || board[x][y] == 1)
            {
                continue;
            }

            mark[x][y] = 1;

            q.push({ x,y });

        }
    }
}

//bfs问题，寻找栖息地

int main()
{
    cin >> n;

    for (int i = 0;i < n;i++)
    {
        for (int j = 0;j < n;j++)
        {
            cin >> board[i][j];
            if ((i == 0 || i == n - 1 || j == 0 || j == n - 1) && board[i][j] == 0)
            {
                q.push({ i,j });
            }
        }
    }

    bfs();

    for (int i = 0;i < n;i++)
    {
        for (int j = 0;j < n;j++)
        {
            if (!mark[i][j] && board[i][j] == 0)
            {
                cout << 2 << " ";
            }
            else
            {
                cout << board[i][j] << " ";
            }
        }
    }

    return 0;
}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include<queue>

using namespace std;

typedef pair<int, int> PII;

int m = 0;

const int N = 310;

int g[N][N];
queue<PII>q;
int dist[N][N];
int mark[N][N];//存流星砸到的点

int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };

int bfs()
{
    q.push({ 0,0 });
    dist[0][0] = 0;

    while (q.size())
    {
        auto t = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int a = t.first + dx[i];
            int b = t.second + dy[i];

            //控边界
            if (a < 0 || b < 0) continue;

            //走过的路不再走
            if (dist[a][b] > 0) continue;

            //如果流星已经砸了就走不了/被砸死
            if (dist[t.first][t.second] + 1 >= mark[a][b]) continue;

            dist[a][b] = dist[t.first][t.second] + 1;
            q.push({ a,b });

            //如果发现走到的位置没有流星砸，返回
            if (mark[a][b] > 1e9) return dist[a][b];
        }
    }
    return -1;
}

int main()
{
    scanf("%d", &m);
    memset(mark, 0x3f, sizeof(mark));
    while (m--)
    {
        int x, y, t;
        scanf("%d %d %d", &x, &y, &t);
        mark[x][y] = min(t, mark[x][y]);//流星砸到的中心点
        for (int i = 0; i < 4; i++)
        {
            int a = dx[i] + x;
            int b = dy[i] + y;

            if (a < 0 || a > 300 || b < 0 || b > 300) continue;

            mark[a][b] = min(t, mark[a][b]);//往外延伸的四个点
        }
    }
    int res = bfs();
    printf("%d", res);
    return 0;

}

//日期累加
#include <cstdio>
#include <iostream>
using namespace std;

int m;
int year, month, day, days;
int months[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };

int main() {

    cin >> m;
    while (m--)
    {
        cin >> year >> month >> day >> days;

        while (days)
        {
            if ((year % 400 == 0) || (year % 100 != 0 && year % 4 == 0))
            {
                if (days < months[month])
                {
                    break;
                }
                else if (month == 2)
                {
                    if (days < months[month] + 1)
                    {
                        break;
                    }
                }

                if (month == 2)
                {
                    days -= (months[month] + 1);
                }
                else {
                    days -= months[month];
                }

                month++;
            }
            else
            {
                if (days < months[month])
                {
                    break;
                }

                days -= months[month];
                month++;
            }

            if (month > 12)
            {
                year++;
                month = month - 12;
            }
        }

        if (days + day > months[month])
        {
            day = days + day - months[month++];
        }
        else {
            day += days;
        }

        printf("%d-%02d-%02d\n", year, month, day);
    }


}

//修剪灌木
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 10000;
int trees[N];
int n;



int main()
{
    cin >> n;

    for (int i = 1;i <= n;i++)
    {
        cout << 2 * max((n - i), (i - 1)) << endl;
    }


    return 0;
}

//刷题时间
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

long long a, b, n, ret;


int main()
{
    cin >> a >> b >> n;

    long long week = n / (a * 5 + b * 2);
    ret += week * 7;
    n -= week * (a * 5 + b * 2);

    for (int i = 0;i < 5 && n>0;i++) n -= a, ret++;

    for (int i = 0;i < 2 && n>0;i++) n -= b, ret++;


    cout << ret << endl;

    return 0;
}

//并查集
class Solution {
public:
    static const int N = 100;
    int couple[N];
    int sets;

    void built(int num)//构建时自己就是自己的祖先
    {
        for (int i = 0;i < num;i++)
        {
            couple[i] = i;
        }
        sets = num;
    }

    int Find(int num)
    {
        if (couple[num] == num)
        {
            return num;
        }

        couple[num] = Find(couple[num]);
        return couple[num];



    }


    void Union(int a, int b)
    {
        int i = Find(a);
        int j = Find(b);

        if (i != j)
        {
            couple[i] = j;
            sets--;

        }
    }



    int minSwapsCouples(vector<int>& row) {

        int rown = row.size();
        built(rown / 2);
        int res = 0;
        for (int i = 0;i < rown;i += 2)
        {
            Union(row[i] / 2, row[i + 1] / 2);
        }

        res = rown / 2 - sets;

        return res;
    }
};

//和为k的连续子数组的个数
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {

        unordered_map<int, int>hash;
        int sum = 0, ret = 0;
        hash[0] = 1;

        for (auto e : nums)
        {
            sum += e;
            if (hash[sum - k])
            {
                ret += hash[sum - k];
            }

            hash[sum]++;
        }

        return ret;

    }
};

//二维前缀和
class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {

        int m = mat.size();
        int n = mat[0].size();
        vector<vector<int>>dp(m + 1, vector<int>(n + 1, 0));
        vector<vector<int>>answer(m, vector<int>(n, 0));

        for (int i = 1;i <= m;i++)
        {
            for (int j = 1;j <= n;j++)
            {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }

        for (int i = 0;i < m;i++)
        {
            for (int j = 0;j < n;j++)
            {
                int x1 = (i - k) < 0 ? 0 : i - k;
                int y1 = (j - k) < 0 ? 0 : j - k;

                int x2 = (i + k) > (m - 1) ? m - 1 : i + k;
                int y2 = (j + k) > (n - 1) ? n - 1 : j + k;

                int sum = dp[x2 + 1][y2 + 1] - dp[x2 + 1][y1] - dp[x1][y2 + 1] + dp[x1][y1];
                answer[i][j] = sum;
            }
        }

        return answer;

    }
};

//找到字符串的最小异位词
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {

        unordered_map<char, int>hash1, hash2;

        for (auto e : p)
        {
            hash2[e]++;
        }

        int n = s.size();
        int count = 0; vector<int>ret;

        for (int left = 0, right = 0;right < n;right++)
        {
            hash1[s[right]]++;
            if (hash1[s[right]] <= hash2[s[right]])
            {
                count++;
            }


            if (right - left + 1 > p.size())
            {
                if (hash1[s[left]]-- <= hash2[s[left]])
                {
                    count--;
                }
                left++;
            }


            if (count == p.size())
            {
                ret.push_back(left);
            }

        }

        return ret;

    }
};

//串联所有单词的子串
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {

        vector<int>ret;
        unordered_map<string, int>hash1;
        for (auto e : words)
        {
            hash1[e]++;
        }
        int n = words.size(), len = words[0].size();
        if (s.size() < len * n)
        {
            return ret;
        }

        for (int i = 0;i < len;i++)
        {
            unordered_map<string, int>hash2;
            int count = 0;
            for (int left = i, right = i;right <= s.size() - len;right += len)
            {
                string str = s.substr(right, len);
                if (++hash2[str] <= hash1[str])//进窗口,统计有效值
                {
                    count++;
                }

                while (right - left + 1 > len * n)
                {
                    string str1 = s.substr(left, len);
                    if (hash2[str1]-- <= hash1[str1])
                    {
                        count--;
                    }
                    left += len;
                }

                if (count == n)
                {
                    ret.push_back(left);
                }
            }
        }

        return ret;

    }
};

//除自身以外数组的乘积
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {

        int n = nums.size();
        vector<int>f(n + 1, 1);
        vector<int>b(n + 1, 1);

        for (int i = 1;i <= n;i++)
        {
            f[i] = f[i - 1] * nums[i - 1];
        }

        for (int i = n - 2;i >= 0;i--)
        {
            b[i] = b[i + 1] * nums[i + 1];
        }

        vector<int>answer;

        for (int i = 0;i < n;i++)
        {
            answer.push_back(f[i] * b[i]);
        }

        return answer;

    }
};

//丢失的数字
class Solution {
public:
    int missingNumber(vector<int>& nums) {

        int num = 0;
        int n = nums.size();
        for (int i = 0;i <= n;i++)
        {
            num ^= i;
        }

        for (auto e : nums)
        {
            num ^= e;
        }

        return num;

    }
};

//只出现一次的数字
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        long long ret = 0;
        for (int i = 0;i < 32;i++)
        {
            long long sum = 0;
            for (auto e : nums)
            {
                sum += e & (1 << i);
            }
            if (sum % 3)
            {
                ret ^= (1 << i);
            }
        }
        return ret;
    }
};

//消失的数字
class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {

        int N = nums.size();

        int tmp = 0;
        for (auto e : nums)
        {
            tmp ^= e;
        }

        for (int i = 1;i <= N + 2;i++)
        {
            tmp ^= i;
        }

        int pos = 0;
        for (;pos < 32;pos++)
        {
            if (tmp & (1 << pos))
            {
                break;
            }
        }


        int a = 0, b = 0; vector<int>ret;

        for (int i = 1;i <= N + 2;i++)
        {
            if (i & (1 << pos))
            {
                a ^= i;
            }
            else
            {
                b ^= i;
            }
        }

        for (auto e : nums)
        {
            if (e & (1 << pos))
            {
                a ^= e;
            }
            else
            {
                b ^= e;
            }

        }

        ret.push_back(a), ret.push_back(b);

        return ret;

    }
};

//Z字形变换
class Solution {
public:
    string convert(string s, int n) {

        if (n == 1)
        {
            return s;
        }

        string ret = "";
        for (int i = 0;i < n;i++)
        {
            int d = 2 * n - 2;
            if (i == 0 || i == n - 1)
            {
                int k = 0;
                while (i + k * d < s.size())
                {
                    ret += s[i + k * d];
                    k++;
                }
            }
            else
            {
                int k = 0;
                while (k * d + i < s.size())
                {
                    ret += s[k * d + i];
                    if ((k * d + d - i) < s.size())
                    {
                        ret += s[k * d + d - i];
                    }

                    k++;
                }
            }
        }

        return ret;
    }
};


//数青蛙
class Solution {
public:
    int minNumberOfFrogs(string C) {

        string str = "croak";
        int n = str.size();
        vector<int>hash(n);//模仿一个hash表

        unordered_map<char, int>index;//记录当前字符的下标
        for (int i = 0;i < n;i++)
        {
            index[str[i]] = i;
        }


        for (auto ch : C)
        {
            if (ch == 'c')
            {
                if (hash[n - 1] == 0)
                {
                    hash[0]++;
                }
                else
                {
                    hash[n - 1]--;
                    hash[0]++;
                }
            }
            else
            {

                int i = index[ch];//先将当前字符的下标算出
                if (hash[i - 1] == 0) return -1;
                hash[i]++, hash[i - 1]--;
            }
        }


        for (int i = 0;i < n - 1;i++)
        {
            if (hash[i] != 0)
            {
                return -1;
            }
        }


        return hash[n - 1];


    }
};

//快速排序
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {

        srand(time(0));
        //快速排序
        qsort(nums, 0, nums.size() - 1);
        //返回数组
        return  nums;
    }

    void qsort(vector<int>& nums, int l, int r)
    {
        //终止条件
        if (l >= r) return;

        //随机数取key
        int key = getrandom(nums, l, r);

        //建议背下来，数组分三块
        int i = l, left = l - 1, right = r + 1;
        while (i < right)
        {
            if (nums[i] < key)
            {
                swap(nums[i++], nums[++left]);
            }
            else if (nums[i] == key)
            {
                i++;
            }
            else
            {
                swap(nums[i], nums[--right]);
            }

        }

        qsort(nums, l, left);
        qsort(nums, right, r);
    }

    int getrandom(vector<int>& nums, int left, int right)//这里加上一个&就过了
    {
        int r = rand();
        return nums[r % (right - left + 1) + left];
    }

};

//逆序对的数量
class Solution {
public:
    int ret = 0;
    vector<int>tmp;

    int reversePairs(vector<int>& record) {

        tmp.resize(record.size());
        mergesort(record, 0, record.size() - 1);
        return ret;

    }

    void mergesort(vector<int>& record, int left, int right)
    {
        if (left >= right) return;
        int mid = (left + right) / 2;

        //先处理左边和右边的
        mergesort(record, left, mid);
        mergesort(record, mid + 1, right);


        int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur1 <= mid && cur2 <= right)
        {
            if (record[cur1] <= record[cur2])
            {
                tmp[i++] = record[cur1++];

            }
            else
            {
                tmp[i++] = record[cur2++];
                //处理当前范围，在左边和右边挑一个元素来组成逆序对
                ret += mid - cur1 + 1;
            }
        }

        while (cur1 <= mid)
        {
            tmp[i++] = record[cur1++];
        }

        while (cur2 <= right)
        {
            tmp[i++] = record[cur2++];
        }

        for (int i = left;i <= right;i++)
        {
            record[i] = tmp[i - left];
        }
    }
};

//重要的翻转对
class Solution {
public:
    int ret = 0;
    vector<int>tmp;

    int reversePairs(vector<int>& record) {

        tmp.resize(record.size());
        mergesort(record, 0, record.size() - 1);
        return ret;

    }

    void mergesort(vector<int>& record, int left, int right)
    {
        if (left >= right) return;
        int mid = (left + right) / 2;

        //先处理左边和右边的
        mergesort(record, left, mid);
        mergesort(record, mid + 1, right);
        int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur2 <= right)
        {
            while (cur1 <= mid && record[cur1] / 2.0 <= record[cur2]) cur1++;

            if (cur1 > mid) break;

            ret += mid - cur1 + 1;

            cur2++;
        }

        cur1 = left, cur2 = mid + 1;

        while (cur1 <= mid && cur2 <= right)
        {
            if (record[cur1] < record[cur2])
            {
                //处理当前范围，在左边和右边挑一个元素来组成逆序对
                tmp[i++] = record[cur1++];

            }
            else
            {
                tmp[i++] = record[cur2++];
            }
        }

        while (cur1 <= mid)
        {
            tmp[i++] = record[cur1++];
        }

        while (cur2 <= right)
        {
            tmp[i++] = record[cur2++];
        }

        for (int i = left;i <= right;i++)
        {
            record[i] = tmp[i - left];
        }
    }
};

//翻转链表
class Solution {
public:
    ListNode* reverseList(ListNode* head) {

        if (head == nullptr || head->next == nullptr) return head;

        ListNode* NewHead = reverseList(head->next);

        head->next->next = head;
        head->next = nullptr;

        return NewHead;

    }
};

//叶子上的和
class Solution {
public:

    int sumNumbers(TreeNode* root) {
        return Sum(root, 0);
    }

    int Sum(TreeNode* root, int presum)
    {
        //
        presum = presum * 10 + root->val;

        //遇到叶子节点返回 
        if (root->left == nullptr && root->right == nullptr) return presum;

        int ret = 0;

        if (root->left) ret += Sum(root->left, presum);
        if (root->right) ret += Sum(root->right, presum);
        return ret;

    }

};

//验证搜索二叉树
class Solution {
public:

    long long pre = -2147483649;
    bool isValidBST(TreeNode* root) {

        if (root == nullptr) return true;


        bool L = isValidBST(root->left);

        if (!L) return false;

        bool cur = false;

        if (root->val > pre) cur = true;

        if (cur == false) return false;

        pre = root->val;

        bool R = isValidBST(root->right);

        if (!R) return false;


        return L && R && cur;

    }
};

//全排列II
class Solution {
public:

    vector<vector<int>>ret;
    vector<int>path;
    bool used[10];
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        dfs(nums, 0);
        return ret;
    }

    void dfs(vector<int>& nums, int pos)
    {
        if (path.size() == nums.size())
        {
            ret.push_back(path);
            return;
        }

        for (int i = 0;i < nums.size();i++)
        {
            if (!used[i] && (i == 0 || nums[i] != nums[i - 1] || used[i - 1] == true))
            {
                path.push_back(nums[i]);
                used[i] = true;
                dfs(nums, pos + 1);
                path.pop_back();
                used[i] = false;
            }
        }
    }
};

//组合总和
class Solution {
public:
    vector<vector<int>>ret;
    vector<int>path;
    int sum = 0;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates, target, 0);
        return ret;
    }

    void dfs(vector<int>& candidates, int target, int pos)
    {
        if (sum >= target)
        {
            if (sum == target)
            {
                ret.push_back(path);
            }
            return;
        }

        for (int i = pos;i < candidates.size();i++)
        {
            sum += candidates[i];
            path.push_back(candidates[i]);
            dfs(candidates, target, i);
            sum -= candidates[i];
            path.pop_back();
        }
    }
};

//N皇后问题
class Solution {
public:

    vector<vector<string>>board;
    vector<string>path;
    bool col[10], dig1[20], dig2[20];
    int num;
    vector<vector<string>> solveNQueens(int n) {

        num = n;
        path.resize(n);
        for (int i = 0;i < n;i++)
        {
            path[i].append(n, '.');
        }

        dfs(0);

        return board;
    }

    void dfs(int row)
    {

        if (row == num)
        {
            board.push_back(path);
            return;
        }

        for (int i = 0;i < num;i++)
        {
            if (!col[i] && !dig1[row - i + num] && !dig2[row + i])
            {
                path[row][i] = 'Q';
                col[i] = dig1[row - i + num] = dig2[row + i] = true;
                dfs(row + 1);
                path[row][i] = '.';
                col[i] = dig1[row - i + num] = dig2[row + i] = false;
            }
        }

    }
};

//岛屿的数量
class Solution {
public:

    bool used[301][301];
    int m, n;
    int dx[4] = { 0,0,-1,1 }, dy[4] = { 1,-1,0,0 };
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size(), n = grid[0].size();
        int count = 0;
        for (int i = 0;i < m;i++)
        {
            for (int j = 0;j < n;j++)
            {
                if (!used[i][j] && grid[i][j] == '1')
                {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }

        return count;
    }

    void dfs(vector<vector<char>>& grid, int i, int j)
    {
        for (int k = 0;k < 4;k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && !used[x][y] && grid[x][y] == '1')
            {
                used[x][y] = true;
                dfs(grid, x, y);
            }
        }
    }
};

//机器人的路
class Solution {
public:

    vector<vector<int>>dp;
    int uniquePaths(int m, int n) {

        dp.resize(m + 1, vector<int>(n + 1, 0));
        dp[0][1] = 1;

        for (int i = 1;i <= m;i++)
        {
            for (int j = 1;j <= n;j++)
            {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }


        return dp[m][n];
    }


};

//太平洋大西洋流水问题
lass Solution{
public:

     int m,n;

    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {

     m = heights.size(),n = heights[0].size();
     vector<vector<bool>>p(m,vector<bool>(n,false));
     vector<vector<bool>>a(m,vector<bool>(n,false));
     vector<vector<int>>ret;
     for (int i = 0;i < m;i++)
     {
        dfs(i,0,heights,p);
     }

     for (int i = 0;i < m;i++)
     {
         dfs(i,n - 1,heights,a);
     }

     for (int i = 0;i < n;i++)
     {
        dfs(0,i,heights,p);
     }

    for (int i = 0;i < n;i++)
     {
        dfs(m - 1,i,heights,a);
     }

     for (int i = 0;i < m;i++)
     {
        for (int j = 0;j < n;j++)
        {
            if (p[i][j] && a[i][j])
            {
                ret.push_back({i,j});
            }
        }
     }

     return ret;

    }

    int dx[4] = {0,0,1,-1},dy[4] = {-1,1,0,0};
    void dfs(int i,int j,vector<vector<int>>& heights,vector<vector<bool>>& board)
    {
       board[i][j] = true;

       for (int k = 0;k < 4;k++)
       {
         int x = i + dx[k],y = j + dy[k];
         if (x >= 0 && x < m && y >= 0 && y < n && !board[x][y] && heights[x][y] >= heights[i][j])
         {
             dfs(x,y,heights,board);
         }
       }
    }
};

//重排链表
class Solution {
public:
    void reorderList(ListNode* head) {

        if (head == nullptr || head->next == nullptr || head->next->next == nullptr)
        {
            return;
        }

        ListNode* slow = head;
        ListNode* fast = head;

        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        ListNode* head2 = nullptr;
        if (slow)
        {

            head2 = reverse(slow->next);
            slow->next = nullptr;
        }
        ListNode* head1 = head;
        ListNode* Next1 = head->next;
        ListNode* Next2 = head2->next;

        while (head2)
        {
            head1->next = head2;
            head2->next = Next1;
            head1 = Next1;
            head2 = Next2;
            if (head1) Next1 = head1->next;
            if (head2)Next2 = head2->next;

        }

    }

    ListNode* reverse(ListNode* head)
    {
        if (head == nullptr || head->next == nullptr)  return head;

        ListNode* NewHead = reverse(head->next);

        head->next->next = head;
        head->next = nullptr;

        return NewHead;
    }


};

//k个一组翻转
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {

        int count = 0;
        ListNode* l = head;
        while (l)
        {
            l = l->next;
            count++;
        }

        int n = count / k;
        ListNode* head2 = new ListNode(0);
        head2->next = nullptr;

        ListNode* tmp = head2;
        ListNode* pre = head2;
        ListNode* n1 = head2;
        ListNode* cur = head2;
        for (int i = 0;i < n;i++)
        {

            for (int j = 0;j < k;j++)
            {
                n1 = pre->next;
                cur = head;
                head = head->next;
                pre->next = cur;
                cur->next = n1;
            }

            while (tmp->next)
            {
                tmp = tmp->next;
            }

            pre = tmp;

        }

        ListNode* tail = head2;
        while (tail->next)
        {
            tail = tail->next;
        }

        tail->next = head;

        return head2->next;



    }
};

//最长公共前缀
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs)
    {
        if (strs.size() == 1) return strs[0];
        string str = "", ret = "";
        for (int i = 1;i < strs.size();i++)
        {
            str = FindCommon(strs[i], strs[i - 1]);
            if (str.size() == 0) return "";

            if (ret.size() == 0) ret = str;
            else if (ret.size() > str.size()) ret = str;
        }
        return ret;
    }

    string FindCommon(string& str1, string& str2)
    {
        int len = str1.size() < str2.size() ? str1.size() : str2.size();
        int i = 0;

        for (i = 0;i < len;i++)
        {
            if (str1[i] != str2[i])
            {
                break;
            }
        }
        return str1.substr(0, i);
    }
};

//高精度乘法
class Solution {
public:
    string multiply(string num1, string num2) {

        int m = num1.size(), n = num2.size();
        vector<int>nums(m + n - 1);
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        //无进位相加
        for (int i = 0;i < m;i++)
        {
            for (int j = 0;j < n;j++)
            {
                nums[i + j] += (num1[i] - '0') * (num2[j] - '0');
            }
        }

        string ret;
        int t = 0, cur = 0;
        while (cur < n + m - 1 || t)
        {

            if (cur < m + n - 1)
            {
                int sum = nums[cur++] + t;
                ret += sum % 10 + '0';
                t = sum / 10;
            }
            else
            {
                ret += t + '0';
                t /= 10;
            }

        }

        while (ret.size() > 1 && ret.back() == '0') ret.pop_back();

        reverse(ret.begin(), ret.end());
        return ret;

    }
};

//二叉树的最大宽度
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {

        if (root == nullptr) return 0;
        vector<pair<TreeNode*, unsigned int>> q;
        q.push_back({ root,0 });
        unsigned int Max = 0;

        while (q.size())
        {
            auto& [x1, y1] = q[0];
            auto& [x2, y2] = q.back();
            Max = max(Max, (int)y2 - y1 + 1);
            vector<pair<TreeNode*, unsigned int>>tmp;
            for (auto& [x, y] : q)
            {
                if (x->left) tmp.push_back({ x->left,2 * y });
                if (x->right) tmp.push_back({ x->right,2 * y + 1 });
            }

            q = tmp;
        }

        return Max;
    }
};

//数据流的中位数
class MedianFinder {
public:
    priority_queue<int>left;//大根堆
    priority_queue<int, vector<int>, greater<int>>right;//小根堆

    MedianFinder()
    {

    }

    void addNum(int num) {

        if (left.size() == right.size())
        {
            if (left.size() == 0 || num <= left.top())
            {
                left.push(num);
            }
            else if (num > left.top())
            {
                right.push(num);
                int y = right.top();
                right.pop();
                left.push(y);
            }
        }
        else
        {
            if (num > left.top())
            {
                right.push(num);
            }
            else
            {
                left.push(num);
                int x = left.top();
                left.pop();
                right.push(x);
            }
        }

    }

    double findMedian() {
        if (left.size() == right.size())
        {
            return (left.top() + right.top()) / 2.0;
        }

        return left.top();
    }
};

//矩阵
class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {

        int m = mat.size(), n = mat[0].size();
        vector<vector<int>>dist(m, vector<int>(n, 0));
        queue<pair<int, int>>q;

        for (int i = 0;i < m;i++)
        {
            for (int j = 0;j < n;j++)
            {
                if (mat[i][j] == 0) q.push({ i,j });
            }
        }

        int dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,-1,1 };

        while (q.size())
        {
            int sz = q.size();
            for (int i = 0;i < sz;i++)
            {
                auto [a, b] = q.front();
                q.pop();

                for (int k = 0;k < 4;k++)
                {
                    int x = a + dx[k], y = b + dy[k];
                    if (x >= 0 && x < m && y >= 0 && y < n && mat[x][y] && !dist[x][y])
                    {
                        dist[x][y] = dist[a][b] + 1;
                        q.push({ x,y });
                    }
                }
            }
        }

        return dist;


    }
};